Variable-length encoding is widely employed so as to compress an image and music. The variable-length encoding is an encoding method of assigning a shorter codeword to a symbol with a higher probability. The variable-length encoding has a feature that an average word length of codewords can be reduced. A method of decoding information encoded by such variable-length encoding can be classified into the following four methods: (a) a simple table lookup method; (b) a leading sign count method; (c) a binary tree method; and (d) a prefix grouping method. Though these designations are not common designations for decoding methods, these designations are herein used. These methods are briefly described below.
The (a) simple table lookup method is the simplest method. Suppose that the word length of a longest codeword is N bits. Then, the N bits are extracted from the head of an input bit sequence. Then, using those N bits as an index, an element is extracted from a table including 2^N elements. The element extracted from the table is a symbol corresponding to the codeword. This method has a disadvantage that the size of the table is large.
In the (b) leading sign count method, the group of a codeword is decoded, based on the number of contiguous sign bits (1s or 0s) at the head of an input bit sequence. M bits that follow the sign bits at the head of the input bit sequence are extracted, and using the M bits, the codeword is decoded. A number M is usually four, five, or the like, and changes according to the structure of codewords. However, there are some useless data in a table for decoding a codeword using the M bits. The size of the table in the (b) leading sign count method is smaller than that in the (a) simple table lookup method. However, according to the structure of codewords, two kinds of tables (for code lengths and symbols) sometimes become necessary. Most software variable-length decoders employ this method.
The (c) binary tree method is a decoding method in which a binary tree indicating a codeword is traced for every bit. When a leaf of the tree is arrived at, a symbol is decoded by referring to a table or the like. Though this method has a disadvantage that a throughput (of one bit per cycle) in this method is lower than that in other decoding method, this method is suitable for dedicated hardware implementation.
The (d) prefix grouping method is a decoding method based on a fact that “a codeword is divided into a prefix and a suffix”. An input bit sequence is compared with prefixes of all codewords, and examines which prefix the input bit sequence has. Since the prefix and a code length of a codeword correspond in a one-to-one relationship, the code length can also be automatically known when the prefix can be identified. When the prefix of the input bit sequence is determined, the suffix is extracted from the input bit sequence. When the prefix and the suffix could be identified, an offset for referring to a table can be obtained. Then, using the offset, the table is searched and a symbol corresponding to the codeword is extracted. This prefix grouping method is described in Patent Documents 1 and 2, and Non-patent Documents 1 and 2.
The size of the table in the prefix grouping method is smaller than that in the (b) leading sign count method. The table size in the prefix grouping method is substantially equivalent to the number of symbols. Generally, it is difficult to execute processing of comparing the input bit sequence with the prefixes and processing of computing the offset from the prefix and the suffix, by software. Accordingly, this method is suitable for dedicated hardware implementation.
Patent Document 1: JP Patent Kokai Publication No. JP-A-07-235878
Patent Document 2: JP Patent Kohyo Publication No. JP-P-2002-516501A
Non-patent Document 1: Bai-Jue Shieh et al., “A New Approach of Group-Based VLC codec System with Full Table Programmability,” IEEE Transactions on Circuits and Systems for Video Technology, Vol. 11, No. 2, February 2001.
Non-patent Document 2: Cheng-Teh Hsieh et al., “A Concurrent Memory-efficient VLC Decoder for MPEG Applications,” IEEE Transactions on Consumer Electronics, Vol. 42, August 1996.
All descriptions of the Patent Documents and the Non-patent Documents described above are regarded as being incorporated herein by reference and described.